Prefetching is a technique that is commonly used in connection with database management systems (DBMS's) and other data storage and retrieval systems. Prefetching substantially improves the performance of queries and data manipulation language (DML) statements by reducing the amount of time required to perform input/output operations. Specifically, prefetching may enable a single processing thread to keep multiple disks active. Prefetching may also enable central processing unit (CPU) and I/O parallelism by issuing asynchronous input/output operations.
Prefetching is typically performed using a special prefetch iterator, which may be implemented by a DBMS query optimizer. The prefetch iterator may be inserted on the outer side of a nested loop join where the inner side of the join contains a correlated range scan. The prefetch iterator may also be inserted as the input to an insert, update, or delete iterator. The prefetch iterator may buffer a large quantity of rows, which may vary depending on factors such as, for example, the version of the DBMS and the amount of available memory. The prefetch operator then issues prefetch requests based on the buffered rows. As these input/output operations complete, the corresponding rows are returned to a prefetch consumer iterator such as, for example, a range or DML iterator.
Although it dramatically improves input/output operation performance, there are a number of drawbacks related to conventional prefetching. For example, if the prefetch iterator requires a page that is not in the buffer pool, then the prefetch operation stalls and waits until the missing page becomes available. During this waiting period, other input/output operations or return rows for completed input/output operations may be issued. Importantly, once the missing page becomes available, the prefetch iterator resumes the prefetch operation from its original initiation point (i.e. a root node), thereby repeating the same page searches that have already been completed. Such repetition increases the processing time for the prefetch operation, and, if the prefetch iterator encounters multiple page misses, then the delay due to repetition is multiplied.
An exemplary prefetch operation that encounters a missing page is depicted in FIG. 1. The prefetch operation traverses node structure 101 which may be, for example, a b tree or a version store. The prefetch operation target data may be, for example, disk pages identified by a list of key values. The target data is located in leaf node 101h, as indicated by the node's square shape. The prefetch operation is initiated at root node 101a and continues through second level node 101b, as shown by the thick lines and directional arrows indicating the prefetch path. Third level node 101d is a missing node, as indicated by the dashed lines surrounding the node. Thus, when the prefetch reaches missing node 101d, the operation stalls and waits for missing node 101d to become available. When node 101d becomes available, the prefetch resumes from root node 101a rather than node 101d, thereby repeating the traversal of nodes 101a and 101b. 
Another drawback of conventional prefetching is that, once a prefetch operation is completed, the prefetch consumer iterator duplicates the entire node structure traversal performed by the prefetch iterator. For example, after a prefetch iterator traverses nodes 101a to 101h as shown in FIG. 2, the prefetch consumer iterator will repeat the entire same traversal. The repeated traversal of nodes 101a, 101b, 101d, and 101f could be eliminated by initiating the prefetch consumer operation directly from node 101h rather than from root node 101a. 
Yet another drawback of conventional prefetching is that it fails to exploit ordered key lists. Specifically, for such ordered key lists, it is likely that each key will be located on a page that is either identical or in very close proximity to the page of the proceeding key in the list. For example, referring again to FIG. 2, if a third key is located in leaf node 101h, then it is highly likely that a fourth key will be located either in leaf node 101f or in sibling leaf node 101i. However, despite this ordered relationship, in conventional prefetch operation are always initiated from root node 101a. If, as is likely, the fourth key is located in nodes 101f or 101i, then the traversal of nodes 101a, 101b, 101d, and 101f will be repeated.
Thus, there is a need in the art for systems and methods for improved prefetching that eliminate the drawbacks of conventional prefetching. The present invention satisfies these and other needs.